===========================================================================
                        About DNET -- Dan Suthers
===========================================================================
; 
;                          USER'S DOCUMENTATION
;
;  A discrimination net facility lets one do several things:
;
;  - 'Uniquify' list expressions under EQ by allowing one to retrive a stored
;    expression using an EQUAL expression as the key.
;  - Associate properties with list expressions (using the above capability).
;  - Ask whether a particular expression has been stored in a data base.
;  - Retrieve expressions by pattern matching using variables in either the
;    retrieval key or in the stored expressions.
;  - Change contexts efficiently by changing the discrimination net in use.
;
;  A discrimination net may be used to implement a simple data base, or to
;  support more sophisticated systems for deductive retrieval, forward and
;  backward chaining of rules, and/or truth maintenance.  The present package
;  attempts to be simple, general, and efficient by providing the most basic
;  operations efficiently implemented without frills.
;
;  Most operations take the discrimination net as their last argument.  This
;  facilitates context switching.  Storage of dotted lists is not allowed, 
;  due to the indexing method used.  Pattern matching retrieval processes 
;  variables in either the query pattern (MATCH-PATTERN) or the network 
;  (MATCH-EXPRESSION), or both (MATCH). The general MATCH function is less 
;  efficient, and most applications only need to match in one direction.
;
;  When a new expression is added via INDEXPR, some applications will need 
;  to do special processing of the expression and/or its dnet-terminal.  If 
;  this were left to the application after the INDEXPR call returned, this 
;  processing could not be done on expressions loaded from a file saved by 
;  SAVE-DNET, since the latter writes calls to INDEXPR with no surrounding 
;  application-specific forms.  The solution is to have an INDEXPR-HOOK, 
;  which when non-nil is a lambda called on all newly indexed expressions 
;  and their dnet-terminals.  There is also a corresponding DELEXPR-HOOK.
;
; Discrimination Net Operations:  
;    MAKE-DNET makes new ones.
;    RESET-DNET resets to empty and modifies associated info.
;    DNET-INFO associates information with a dnet.
;    ALL-EXPRESSIONS returns all expressions in a dnet (slow).
;    MAP-DNET-TERMINALS maps a function across all dnet-terminals in a dnet.
;    DESTROY-DNET undefines and deallocates a dnet.
;    SAVE-DNET saves a dnet to a file (slow).
;  (Functions requiring retrieval of all expressions are slow because DNET is
;  optimized for balancing fast access to single expressions with space economy.)
; 
; Expression-Based Operations:
;  These do not process variables (treat variables like any other atom).
;   INDEXPR puts an expression in a dnet.
;   GETEXPR retrieves an expression from a dnet.
;   DELEXPR deletes an expression from a dnet.
;   EXPR-INFO associates information with an expression in a dnet.
;
; Pattern-Based Operations:
;  A pattern is a symbolic expression which may contain variables.  
;  Variables are symbols in the package ?.  It is recommended that
;  one declare all variables before use with the (defvariable <sym>) form.
;  No symbol should ever be uninterned from ? by another program.
;   DEFVARIABLE defines a variable.
;   VARIABLE-P tests whether an object is a variable. 
;   PATTERN-P tests whether an object is an expression containing a variable.
;   VARIABLES-IN-PATTERN returns a list of variables in a pattern.
;   MATCH retrieves patterns (or expressions) matching a given pattern (expression).
;   MATCH-PATTERN retrieves expressions matching a given pattern.
;   MATCH-EXPRESSION retrieves patterns matching a given expression.
;   BIND-VARS does the variable binding (restricted unification) for one-way
;     match candidates, and is exported for its potential usefulness.
;   UNIFY does bidirectional variable binding (for MATCH), and is exported.
;   SUBSTITUTE-BINDINGS substitutes for variables in a pattern to give an
;     expression, given a binding list.
;
; NOTE ON BEHAVIOR -- The following behavior is CORRECT:
;
;   ? (dnet:make-dnet :test-dnet)
;   ? (dnet:indexpr '(a b c) :test-dnet)
;   ? (dnet:indexpr '(a ?:x c) :test-dnet)
;   ? (dnet:indexpr '(a ?:y c) :test-dnet)
;   ? (dnet:indexpr '(a (?:x y z) c) :test-dnet)
;
;   ? (dnet:match-pattern '(a ?:x c) :test-dnet)
;   ((A (?:X Y Z) C) (A ?:Y C)     (A ?:X C)     (A B C))
;   (((?:X ?:X Y Z)) ((?:X . ?:Y)) ((?:X . ?:X)) ((?:X . B)))
;
;   ? (dnet:match-expression '(a ?:x c) :test-dnet)
;   ((A ?:X C)     (A ?:Y C))
;   (((?:X . ?:X)) ((?:Y . ?:X)))
;
;   ? (dnet:match '(a ?:x c) :test-dnet)
;   ((A ?:Y C)    (A ?:X C) (A B C))
;   (((?:X . ?:Y)) NIL      ((?:X . B)))
;   (NIL           NIL      NIL)
;
; MATCH-PATTERN ignores variables in the DNET.  Thus, (?:X Y Z) is a
;   constant list as far as it is concerned, and there is no contradiction
;   to binding ?:X to (?:X Y Z).  This feature may be useful when trying
;   to retrieve patterns without processing their variables.
; MATCH-EXPRESSION treats the ?:x in the query as a constant, so only
;   returns the patterns in the DNET which match it.  One happens to have
;   a variable which is the same as the constant; the other matches the
;   variable ?:y in DNET to the constant ?:x.
; MATCH will only return patterns which logically unify with the query
;   pattern.  Thus, it is correctly more restrictive than MATCH-PATTERN
;   above, as ?:X cannot be bound to an expression containing itself.
;   While MATCH returns bindings in both directions (the second and third
;   values), (?:Y . ?:X) does not appear in the second binding list for
;   (A ?:Y C) because (?:X . ?:Y) already expressed the binding, "using 
;   up" ?:Y.  I.e., there is no redundancy across the binding lists.

---------------------------------------------------------------------------
  Documentation for Exported Symbols in Package DNET (generated by PDOC):
---------------------------------------------------------------------------

*?-PACKAGE* Exported but undocumented Variable.

*DNET-PACKAGE* Exported but undocumented Variable.

ALL-EXPRESSIONS
 Function:
  all-expressions <dnet>                                           [Function]
  Returns a list of all expressions in the indicated <dnet>.  The outer
  list is constructed fresh and may be hacked.  This is time consuming.

BIND-VARS
 Function:
  bind-vars <pattern> <expression> <bindings>                      [Function]
  Variables are processed in <pattern> but treated as atoms in <expression>.
  <Bindings> should be existing bindings (usually nil). Dotted endings in 
  <pattern> are assumed to be variables, and are processed. Returns two 
  values: T or NIL to flag whether the pattern matches the expression, and 
  a list of bindings which achieve this matching.

BROWSE-DNETS
 Function:
  browse-dnets &optional <build-mode>                              [Function]
  Puts up a discrimination net browser.  If <build-mode> is nil (default), 
  the default button is for pattern retrieval; if T, the default is for
  adding an expression.

DEFVARIABLE
 Function:
  defvariable <sym>                                                   [Macro]
  Interns the name of <sym> in the variable package ?, and exports it.  Use
  to ensure the variable exists before using it in a pattern.  For example,
  (defvariable x) lets us use ?:x as a variable in patterns.

DELEXPR
 Function:
  delexpr <expr> <dnet>                                            [Function]
  Deletes the expression <expr> from <dnet>, calling DELEXPR-HOOK if it
  is defined for the DNET.  Returns a DNET-TERMINAL iff it was deleted.

DESTROY-DNET
 Function:
  destroy-dnet <dnet>                                              [Function]
  Destroys and undefines the entire <dnet>.

DNET
 Function:
  DNET name &key :indexpr-hook :delexpr-hook :info-place) [Macro]
  Expands into CREATE-DNET call.  The first argument
  is the name of the instance, and the remainder are optional keyword
  arguments for uncomputed slot values, using defaults if not given.

DNET-COMPILED-DELEXPR-HOOK Exported but undocumented Function.

DNET-COMPILED-INDEXPR-HOOK Exported but undocumented Function.

DNET-DELEXPR-HOOK Exported but undocumented Function.

DNET-INDEXPR-HOOK Exported but undocumented Function.

DNET-INFO
 Function:
  dnet-info <dnet>                                                    [Macro]
  Setf-able access to the information associated with <dnet>.

DNET-INFO-PLACE Exported but undocumented Function.

DNET-TERMINAL-EXPR Exported but undocumented Function.

DNET-TERMINAL-INFO Exported but undocumented Function.

EXPR-INFO
 Function:
  expr-info <expr> <dnet>                                          [Function]
  Setf-able access to the information associated with <expr> in <dnet>.

GETEXPR
 Function:
  getexpr <expr> <dnet>                                            [Function]
  Use to query whether <expr> has been stored in <dnet>, and to obtain the
  name of its dnet-terminal.  Returns two values: the expression originally
  stored in <dnet> (and is EQUAL to <expr>), and the dnet-terminal structure.
  Both values are Nil if <expr> is not found. Variables are not processed.

INDEXPR
 Function:
  indexpr <expr> <dnet> &optional <info>                           [Function]
  Ensures that <expr> is stored in <dnet>.  If the <expr> was not already
  in <dnet>, initializes the associated information to <info> (if it was 
  provided), and calls compiled-new-expr-hook (if non-nil) on <expr> and 
  its dnet-terminal.  The latter allows application-specific processing of 
  new expressions. Returns two values: the first is a predicate, T iff <expr> 
  was newly added by this call; and the second is the dnet-terminal structure.

MAKE-DNET
 Function:
  make-dnet <name> &key <indexpr-hook> <delexpr-hook> <info>       [Function]
   Returns a new (empty) discrimination net.  A name is generated unless
   a symbol <name> is provided.  <Indexpr-hook> and <delexpr-hook> are
   assumed to be lambda forms of two arguments which may be compiled.
   These functions are applied to an expression and its corresponding 
   DNET-TERMINAL the first time it is indexed into or deleted from the 
   DNET, respectively. If the optional <info> is provided, the DNET's 
   associated information is initialized to this value.

MAP-DNET-TERMINALS
 Function:
  map-dnet-terminals <f> <dnet>                                     [Function]
  Maps <f> across dnet-terminals in the indicated <dnet>.  Returns NIL.

MATCH
 Function:
  match <pattern> <dnet>                                           [Function]
  For retrieving all patterns unifying with a pattern: variables in both
  are processed.  Returns three values: a list of all patterns in <dnet>
  unifying with the <pattern>, a list of bindings of variables in <pattern>
  to those in the matched patterns, and a list of bindings of variables in
  the matched patterns to those in <pattern>.  The latter two values are
  lists of lists containing pairs (<var> . <exp>), each representing the
  binding of <var> to <exp> (ditto).  Note this is less efficient than
  MATCH-PATTERN and MATCH-EXPRESSION, and should only be used when needed.
  See also documentation for UNIFY.

MATCH-EXPRESSION
 Function:
  match-expression <expression> <dnet>                             [Function]
  For retrieving all patterns (which may contain variables) matching an
  expression.  Returns two values: a list of all patterns in <dnet> 
  matching the <expression>, and a list of respective unifications.  The
  latter is a list of lists containing pairs (<exp-part> . <pat-var>) 
  representing the binding of <pat-var> to <exp-part>, a component of 
  <expression>. Variables in <expression> are treated as constants.

MATCH-PATTERN
 Function:
  match-pattern <pattern> <dnet>                                   [Function]
  For retrieving all expressions matching a pattern which may contain
  variables.  Returns two values: a list of all expressions in <dnet>
  matching the <pattern>, and a list of respective unifications.  The
  latter is a list of lists containing pairs (<pat-var> . <dnet-exp>)
  representing the binding of <pat-var> to <dnet-exp>, a component of
  the corresponding returned expression.  Variables in the dnet are 
  treated as constants.  A special facility provided only by this
  function is dotted variables: any sublist of <pattern> may end in 
  a dot followed by a variable.  This is like &rest binding.

NOT-A-DOTTED-LIST
 Function:
  not-a-dotted-list <expr>                                        [Function]
  Returns T iff there is no non-nil atomic CDR in <expr>.

PATTERN-P
 Function:
  pattern-p <expr>                                                 [Function]
  Returns non-NIL value iff <expr> is or contains a variable.

RESET-DNET
 Function:
  reset-dnet <dnet> &key <indexpr-hook> <delexpr-hook> <info>      [Function]
  Empties an existing discrimination net.  Also enables one to modify
  the hooks and associated info.  See MAKE-DNET.

SAVE-DNET
 Function:
  save-dnet <dnet> <path> &optional (write-in-package :dnet)       [Function]
   Saves expressions required to recreate <dnet> to a file at <path>.
   Returns the <path>.  The file is written in package <write-in-package>,
   or DNET if the optional argument is unspecified. All associated info
   is also saved.   Give <vars> a list of known variables.  This function 
   is slow.

SUBSTITUTE-BINDINGS
 Function:
  substitute-bindings <bindings> <pattern>                         [Function]
  Given <bindings> is an association list as returned by one of the match
  functions, creates an expression from <pattern> where all the variables
  have been replaced by their bindings.  New list structure is used.
  Only makes one pass -- see substitute-transitive-bindings if variables
  may be bound to each other.

SUBSTITUTE-TRANSITIVE-BINDINGS
 Function:
  substitute-bindings <bindings> <pattern>                         [Function]
  Given <bindings> is an association list as returned by one of the match
  functions, creates an expression from <pattern> where all the variables
  have been replaced by their bindings.  New list structure is used.  
  Makes as many passes are needed to eliminate transitivities which may
  be returned by UNIFY when both patterns have variables, such as 
  ((?:y . 3) (?:x . ?:y)) which unifies (?:x ?:x) and (?:y 3).

UNIFY
 Function:
  unify <pattern-1> <pattern-2> &optional <bindings-1> <bindings-2> [Function]
  Given two list/atom patterns (each of which may contain variables), and
  a (usually nil) set of initial bindings, returns three values: 
    1. T or NIL to flag whether the patterns unify;
    2. Bindings of variables in <pattern-1> to elements of <pattern-2>;
    3. Bindings of variables in <pattern-2> to elements of <pattern-1>.
  (The flag is returned first so UNIFY can be used as a predicate.  Since 
  unification can succeed with no bindings, the other values will not serve 
  this function.)  Example:
    (unify '(a ?:x c) '(a (b) ?:y)) ==> T; ((?:X B)); ((?:Y . C))
  Transitivity of bindings is not used for simplification, e.g. you could
  get back T; ((?:X . ?:Y)); ((?:Y . C)). Modified from version by Ken Forbus.
  This function is logically general, and hence checks for a variety of 
  conditions.  It may be inefficient for specialized tasks: I recommend 
  writing a specialized version if any assumptions may be made about the
  patterns to be unified.

VARIABLE-P
 Function:
  variable-p <thing>                                                  [Macro]
  Returns T iff <thing> is a variable (symbol in the ? package).

VARIABLES-IN-PATTERN
 Function:
  variables-in-pattern <pattern>                                   [Function]
  Returns a list of variables occuring in <pattern>.

---------------------------------------------------------------------------
                               EXAMPLE
---------------------------------------------------------------------------

;;; Making a DNET called TEST.

(dnet:make-dnet 'test)
TEST

;;; Adding expressions to the DNET.  INDEXPR returns two values: the first
;;; is T only if the expression is new to the DNET, and the second is the
;;; DNET-TERMINAL structure in which the expression is stored (this is 
;;; returned for code which needs to efficiently access the terminal).

(dnet:indexpr '(a b c) 'test)
T
#((A B C) NIL)

(dnet:indexpr '(junk this one) 'test)
T
#((JUNK THIS ONE) NIL)

;;; Deletion is done by DELEXPR, which returns the DNET-TERMINAL object
;;; of the deleted expression (advanced code may need to operate on it),
;;; or NIL if the expression was not found to delete.

(dnet:delexpr '(junk this one) 'test)
#((JUNK THIS ONE) NIL)

;;; Let's add a few more expressions.

(dnet:indexpr '(a (b) c) 'test)
T
#((A (B) C) NIL)

(dnet:indexpr '(nil) 'test)
T
#((NIL) NIL)

;;; We find out if an expression is in the DNET by using GETEXPR.  It returns
;;; two values.  The first is the expression if found, or NIL if it is not
;;; found.  The second value is the DNET-TERMINAL structure in which the
;;; expression is stored, provided for advanced code which needs efficient
;;; access to it:

(dnet:getexpr '(a b c) 'test)
(A B C)
#((A B C) NIL)

(dnet:getexpr '(junk this one) 'test)
NIL
NIL

;;; Variables are represented as atoms interned in the ? package.  Before
;;; using a variable, we need to make sure it exists, as follows:

(dnet:defvariable x)
T

;;; Now we can see what things in the DNET match a given pattern:

(dnet:match-pattern '(a ?:x c) 'test)
((A B C) (A (B) C))                      ; two things match
(((?:X . B)) ((?:X B)))

;;; MATCH-PATTERN returns two values: a list of all expressions which match
;;; the given pattern, and a list of the bindings which makes the match 
;;; succeed.  Both of these are NIL if there is no match.

(dnet:match-pattern '(not there) 'test)
NIL
NIL

;;; We can also store patterns in the DNET, and match expressions to the
;;; DNET to find out what patterns in the DNET match the given expression.
;;; The returned values are similar:

(dnet:defvariable y)
T

(dnet:indexpr '(a ?:x ?:y) 'test)
T
#((A ?:X ?:Y) NIL)

(dnet:match-expression '(a b c) 'test)
((A B C) (A ?:X ?:Y))                    ; again, two things match
(NIL ((?:Y . C) (?:X . B)))

;;; See DNET-TEST and DNET-RULES for examples of other features of DNET.
;;; The file DNET-ANALYZE has a function which will report on the average
;;; and maximum depth and branching factor of a DNET, to help deal with
;;; efficiency problems.
===========================================================================
